|
In mathematical optimization, a quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic functions. It has the form : where ''P''0, … ''P''''m'' are ''n''-by-''n'' matrices and ''x'' ∈ R''n'' is the optimization variable. If ''P''0, … ''P''''m'' are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If ''P''1, … ''P''''m'' are all zero, then the constraints are in fact linear and the problem is a quadratic program. == Hardness == Solving the general case is an NP-hard problem. To see this, note that the two constraints ''x''1(''x''1 − 1) ≤ 0 and ''x''1(''x''1 − 1) ≥ 0 are equivalent to the constraint ''x''1(''x''1 − 1) = 0, which is in turn equivalent to the constraint ''x''1 ∈ . Hence, any 0–1 integer program (in which all variables have to be either 0 or 1) can be formulated as a quadratically constrained quadratic program. Since 0–1 integer programming is NP-hard in general, QCQP is also NP-hard. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratically constrained quadratic program」の詳細全文を読む スポンサード リンク
|